package 切棍子的最小成本1547;

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public int minCost(int n, int[] cuts) {
        ArrayList<Node> nodes = new ArrayList<>();
        nodes.add(new Node(0, n, n));
        ArrayList<Integer> list = new ArrayList<>();
        for (int i = 0; i < cuts.length; i++) {
            list.add(cuts[i]);
        }
        int sum = 0;
        while (!list.isEmpty()) {
            int min = Integer.MAX_VALUE;
            int index = 0;
            Node node = null;
            for(int i = 0; i < list.size(); i++) {
                int temp = list.get(i);
                for(Node k : nodes) {
                    if (k.l <= temp && k.r >= temp) {
                        if(Math.abs((temp - k.l) - (k.r - temp)) < min) {
                            min = Math.abs((temp - k.l) - (k.r - temp));
                            node = k;
                            index = i;
                            break;
                        }
                    }
                }
                System.out.print(min + " ");
            }
            System.out.println();
            System.out.println(Arrays.toString(list.toArray()));
            nodes.remove(node);
            sum += node.value;
            nodes.add(new Node(node.l, list.get(index), list.get(index) - node.l));
            nodes.add(new Node(list.get(index), node.r, node.r - list.get(index) ));
            list.remove(index);
        }
        return sum;
    }
}
class Node {
    int l;
    int r;
    int value;

    public Node() {}
    public Node(int l, int r, int value) {
        this.l = l;
        this.r = r;
        this.value = value;
    }
}
